package thinking.backtracking;

/**
 * 回溯法 O(n^2) 回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码
 * 对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，
 * 在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢？
 *
 * @author yeyangtao created at 15:24 2020/10/29
 */
public class PackageQuestion {
    //结果放到maxW中
    private int maxW = Integer.MIN_VALUE;
    //物品重量
    private final int[] weight = {2, 2, 4, 6, 3};
    //物品个数
    private final int n = 5;
    //背包承受的最大重量
    private final int w = 9;

    /**
     * f(0,0)调用
     *
     * @param i  物品编号
     * @param cw 当前背包重量
     */
    public void f(int i, int cw) {
        //达到了最大重量 或者放完了物品
        if (cw == w || i == n) {
            if (cw > maxW) maxW = cw;
            return;
        }
        //不装第i个物品
        f(i + 1, cw);
        if (cw + weight[i] <= w) {
            f(i + 1, cw + weight[i]);
        }
    }
}
